package com.markus.code.二叉树.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/11 22:21
 * todo: 二叉树的中序遍历
 */
public class LeetCode_64 {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
    //普通迭代法
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root == null){
            return ans;
        }
        Stack<TreeNode> stack = new Stack<>();
        while(!stack.isEmpty() || root != null){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            ans.add(root.val);
            root = root.right;
        }
        return ans;
    }
    //morris遍历 中序遍历
    public void morrisInOrder(TreeNode root){
        if (root == null){
            return ;
        }
        TreeNode curr = root;
        while(curr != null){
            //System.out.print(curr.val+" ");
            TreeNode mostRight = curr.left;
            //如果当前节点有左子树，就找到左子树的最右子节点
            if (mostRight != null){
                while(mostRight.right != null && mostRight.right != curr){
                    mostRight = mostRight.right;
                }
                //第一次来到这个右子节点
                if (mostRight.right == null){
                    mostRight.right = curr;
                    curr = curr.left;
                    continue;
                }else{
                    mostRight.right = null;
                }
            }
            System.out.print(curr.val+" ");
            curr = curr.right;
        }
    }

    public static void main(String[] args) {
        TreeNode A = new TreeNode(1);
        A.left = new TreeNode(2);
        A.right = new TreeNode(3);
        A.left.left = new TreeNode(4);
        A.left.right = new TreeNode(5);
        A.right.left = new TreeNode(6);
        A.right.right = new TreeNode(7);
        LeetCode_64 demo = new LeetCode_64();
        demo.morrisInOrder(A);
    }
}
